COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\magnification\magstephalf
C00010 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex
\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}
\baselineskip 14pt
\rm
\line{\sevenrm a30.tex[106,phy] \today\hfill}

\bigskip
\ctrline{\bf Computational Geometry}

\bigskip
Given the coordinates of a polygon, how can we compute the area?

\figbox 2truein:

\noindent
It seems hard, so the first thing to do is look at a special case. The
simplest case where the area doesn't go away completely is the triangle.

\figbox 1truein:

\noindent
It's a useful special case; on the one hand, a triangle is a polygon
and on the other, all polygons can be cut into triangles.

\figbox 1.5truein:

\noindent
If we can find a point like $P$ inside the polygon from which all the
edges are visible, we can reduce the area problem for $V↓1V↓2V↓3V↓4$
to the triangles 
$\hbox{area}(PV↓1V↓2)+\hbox{area}(PV↓2V↓3)+\hbox{area}(PV↓3V↓4)+
\hbox{area}(PV↓4V↓1)$. In fact, if we adopt a convention that counterclockwise
polygons have negative area, we can put $P$ anywhere:

\vfill\eject

\figbox 2truein:

$$\eqalign{\hbox{Area}&=\hbox{area}(PV↓1V↓2)+\hbox{area}(PV↓2V↓3)+
\hbox{area}(PV↓3V↓4)-\hbox{area}(PV↓1V↓4)\cr
&=\hbox{area}(PV↓1V↓2)+\hbox{area}(PV↓2V↓3)+\hbox{area}(PV↓3V↓4)+
\hbox{area}(PV↓4V↓1)\,,\cr}$$
where $PV↓4V↓1$ is a counterclockwise triangle of {\sl negative\/} area.

All right, if $P$ can be anywhere, let's put it at the origin. Now what's
the area of $OAB$?

\figbox 2truein:

\noindent
It is $\hbox{area}(OAA↓x)+\hbox{area}(A↓xABB↓x)-\hbox{area}(OBB↓x)
={1\over 2}X↓AY↓B+{1\over 2}(Y↓A+Y↓B)(X↓B-X↓A)-{1\over 2}X↓BY↓B
={1\over 2}(X↓BY↓A-X↓AY↓B)$. Going back to our original polygon,
its area is
$$\eqalign{&\qquad \hbox{area}(OV↓1V↓2)+\hbox{area}(OV↓2V↓3)+\cdots
+\hbox{area}(OV↓{n-1}V↓n)+\hbox{area}(OV↓nV↓1)\cr
\noalign{\smallskip}
&={1\over 2}(X↓2Y↓1-X↓1Y↓2)+{1\over 2}(X↓3Y↓2-X↓2Y↓3)+\cdots +{1\over 2}
(X↓nY↓{n-1}X↓{n-1}Y↓n)+{1\over 2}(X↓1Y↓n-X↓nY↓1)\,.\cr}$$
Collecting the coefficients of each $X↓i$, the area is
$${1\over 2}\bigl(X↓1(Y↓n-Y↓2)+X↓2(Y↓1-Y↓3)+X↓3(Y↓2-Y↓4)+\cdots + X↓n(Y↓{n-1}-Y↓1)
\,.$$
In fact, if we define $Y↓{n+1}=Y↓1$ and $Y↓0=Y↓n$, we get
${1\over 2}\sum↓{i=1}↑NX↓i(Y↓{i-1}-Y↓{i+1})$.

\vfill\eject

\noindent{\bf Exercise.}

Program the calculation of the area of a polygon, using the results above.

\bigskip
\noindent{\bf Exercise.}

Given the coordinates of three points $A$, $B$, $C$, write a program

\figbox 1in:

\noindent
to determine if the path $ABC$ turns left or right, goes straight, or
reverses, at~$B$. (Hint: compute the area of triangle $ABC$.)

\bigskip
\noindent{\bf Exercise.}

Write a program to tell if a given polygon is convex. (Hint: Does it
turn right or left at vertices?)

\bigskip
\noindent{\bf Exercise.}

Given the coordinates of four points $A$, $B$, $C$, $D$, write a program
to determine if $C$ and~$D$ lie on the same side or opposite sides of
the line through $A$ and~$B$.

\figbox 2.5truein:

\line{\qquad Opposite sides\hfil Same sides\qquad}


\noindent
(Hint: Don't forget about areas too quickly.)

\vfill\eject

\bigskip
\noindent{\bf Exercise.}

Given the coordinates of four points $ABCD$, write a program to determine
if the line segments $AB$ and $CD$ cross. (Hint: See the previous exercise.)

\noindent
({\bf Solution:} They cross if $C$ and $D$ are on opposite sides of the line
through $A$ and~$B$, and if $A$ and~$B$ are on opposite sides of the line
through $C$ and~$D$.)

\vfill

\ctrline{Shaded area is locus of $D$ where $CD$ crosses $AB$.}

\eject

\bigskip
\noindent{\bf Exercise.} (Jordan Curve.)

Given the coordinates of the vertices of a polygon:

\disleft 25pt:(1):
Check that it does not cross itself, i.e., that it is a {\sl simple\/} closed
curve.

\disleft 25pt:(2):
Test a sequence of points to see which ones lie inside, outside, or on the
perimeter of the polygon. 

\disleft 25pt::
({\sl Solution:} Draw a line segment to a given point from a point well
away from the polygon, and therefore outside it. If it crosses the perimeter
an odd number of times, the given point is inside. See the previous problem.)

\disleft 25pt::
({\sl Second solution:} Break the polygon up into triangles. Count the number
of positive-area triangles minus the number of negative area triangles
to which the point belongs.)


\bigskip
\parindent0pt
\copyright 1984 Robert W. Floyd

First draft September 10, 1984

\bye